package bTree.LeetCode;

import java.util.*;

public class 单词接龙 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int cnt = 1;
        //用来记录列表元素，有唯一性
        HashSet<String> hashSet = new HashSet<>(wordList);
        //需要记录有没有访问过
        HashSet<String> visited = new HashSet<>();
        visited.add(beginWord);
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        while (!queue.isEmpty()) {
            //大小要提前拿，不然poll了会变化
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String peek = queue.peek();
                //遍历每个字符，进行替换
                char[] charArray = peek.toCharArray();
                for (int i1 = 0; i1 < charArray.length; i1++) {
                    //存起来原来的，要换回去
                    char pre = charArray[i1];
                    for (char c = 'a'; c <= 'z'; c++) {
                        charArray[i1] = c;
                        //注意不能用Arrays.toString
                        String string = new String(charArray);
                        if (hashSet.contains(string) && string.equals(endWord)) {
                            return cnt + 1;
                        }
                        if (hashSet.contains(string) && !visited.contains(string)) {
                            queue.offer(string);
                            //入队就标记
                            visited.add(string);
                        }
                    }
                    charArray[i1] = pre;
                }
                queue.poll();
            }
            cnt++;
        }
        return 0;
    }
}